ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/tsql/doc/tsql.mail/[e-mail] _Thu Apr 8 21:26:07 1993.msg

Internet Message Format | 1996-01-31 | 22KB

Received: from iesd.auc.dk by optima.cs.arizona.edu (5.65c/15) via SMTP
    id AA15069; Thu, 8 Apr 1993 12:26:45 MST
Received: from yellow.iesd.auc.dk by iesd.auc.dk with SMTP id AA21788
  (5.65c8/IDA-1.5/MD for <[e-mail]>); Thu, 8 Apr 1993 21:26:07 +0200
Date: Thu, 8 Apr 1993 21:26:07 +0200
From: "Christian S. Jensen" <[e-mail]>
Message-Id: <[e-mail]>
To: [e-mail]
Subject: TSQL Benchmark, Tasks 1 and 2.

********************************************************************
*                  The TSQL Benchmark Initiative                   *
********************************************************************

Fellow contributors,

In this message, I provide some comments on the most recent postings
to tsql about the TSQL Benchmark. In particular, I focus on a single
comment on the purpose of the benchmark, on the final changes to the
database schema, and on a first comment on the proposed database
instance.

I have also included an up-to-date version of the benchmark document.
Apart from simple renaming of attributes, the database schema is now
frozen. The section on the database instance is now in focus.

On the purpose of the benchmark...
**********************************

> From [e-mail] Fri Apr  2 19:07:44 1993
> On the expressive power....
> _____________________________
> Crist states that the aim of this draft is on user friendliness of
> temporal query languages.  I think the user friendliness and the
> expressive  power of temporal query languages are closely related.
> We should not seperate them.  In this respect we should include
> all the possible queries in the bench mark.  Perhaps, a subset of
> these queries is more common in real life and this subset may be
> a desirable one.  At the earlier stage of the benchmark we place
> our attention on this subset if thw TSLQ community feels that way.

This is close to how I think. Let me just elaborate a bit. User
friendliness is mentioned mainly to indicate that we are not only
looking for as difficult and challenging queries as possible, but are
also interested in ordinary, common queries. A TSQL language must
handle common queries, as well as hard queries, satisfactorily. In the
first version, we are not restricted to easy or hard queries, rather
the restrictions are in other dimensions.

On the final changes to the database schema...
**********************************************

> From [e-mail] Fri Apr  2 19:07:44 1993
> I would propose adding a BUDGET attribute to Mgr relation.  It is a
> temporal attribute and allows comparison between two temporal attributes
> from two different relations.

In my previous summary (April 4), I made some decisions regarding the
database schema. With the exception of these decisions, the schema
design was finalized. As part of the summary, I requested opinions
regarding the inclusion of a Budget attribute.

> Date: Sun, 4 Apr 1993 22:57:12 +0200
> From: "Christian S. Jensen" <[e-mail]>
> This is an interesting suggestion, and I request further comments on
> this. If other contributors feel that this extra attribute allows them
> to formulate types of queries that the existing schema does not allow,
> it would be very useful to hear about that very soon.

Several contributors have later indicated that they also would like a
Budget attribute. Such an attribute has now been added.

Jim, in a recent message, comments on the semantics of the Mgr schema
intended to hold the Budget attribute.

> Date: Tue, 6 Apr 93 13:42:10 EDT
> From: Jim Clifford <[e-mail]>
>
> (2) I was already somewhat confused by the relation currently constituted as
>        MGR (Dept Manager)

First, I briefly explain the original schema, then I consider the
situation after a Budget attribute is introduced.

Before introducing Budget, the schema Mgr = (Dept, Manager) was
intended to relate departments with those employees that are the
managers of the departments. Thus, Mgr models a relationship set
between entity sets of employees and departments, respectively.  A
foreign key constraint (between Manager in Mgr and Name in Emp) was
introduced to indicate that the Emp relation represented the one
connecting entity set. The other entity set, that for departments, was
left out because it was deemed unnecessary.

When Budget is added, we get Mgr = (Dept, Manager, Budget). We must
then ask whether Budget is an attribute of the relationship between
managers and departments or an attribute of departments. Jim favors
the latter (and I agree completely), so now the Mgr relation is about
departments. The final result of these considerations is then this
schema (as requested by Jim):

       Dept = (Department, Manager, Budget)

The attribute Department is the name of the department. This is a
lengthy attribute, and any suggestions for shorter names are welcome.
Also, Dept is now used as an attribute name (in Emp) and as a schema
name. I take it that we want to add the functional dependency
Department --> Budget (a department can only have one budget at any
given point in time).

The changes to the benchmark document implied above are in agreement
with Shashi's recommendations:

> From [e-mail] Thu Apr  8 00:16:33 1993
> From: Shashi K. Gadia <[e-mail]>
> Subject: Benchmark
>
> I also am in favor of Jim Clfford's
> suggestion of treating Name and
> Dept as time invariant keys.
>
> However, I would prefer to keep
> the attribute names for the department
> relation short as suggested by Christian.

Name (of Emp) and Department (of Dept) are primary keys, and we are
looking for shorter attribute names.

On the database instance...
***************************

Finally, Jim raises an unrelated concern. As of now, its impact on the
benchmark document is unclear to me. The following is an attempt to
clarify the situation.

> Date: Tue, 6 Apr 93 13:42:10 EDT
> From: Jim Clifford <[e-mail]>
>
> I believe that the following criterion should be used in
> populating the agreed-upon schema with data:
>
>   the database instance should accord with ALL AND ONLY those
>   constraints which are explicitly stated.
>
> The proposed database instance violates the AND ONLY part of this criterion in
> at least the following way (and possibly others):
...
>
> However, the proposed database also assumes that the "key" attribute
> Name is time-invariant. This is a stronger condition than the notion
> of "key" as a "snapshot function dependency," and biases the proposed
> benchmark in favor of the tuple-stamped models.

It would be of great help if someone (Jim?) could exemplify what is
missing in the current instance. What can we add to the instance in
order not to violate the AND ONLY criterion? Should we add this, or
should we strengthen the constraints?

How do we favor tuple timestamped models? Are we excluding some data
that cannot (easily) be stored in tuple-timestamped models, but may be
stored in other models?

These are all interesting and important questions. Let me add a few
preliminary thoughts.

Jim implies that Name is time-invariant. The question is then with
respect to what? To be specific, consider a schema Emp = (Name, Salary)
with Name --> Salary. The schema may be characterized in at least two
ways.

1. Name is the name of a person, and Salary is the salary of that
person. The notion of time-invariance is then exemplified as follows.
If the person never changes her name then Name is time-invariant.

2. Instances of Emp are simply pairs of text strings and integers,
representing names and salaries, that obey the specified dependency.
In this context, it does not make sense to talk about whether Name is
time-invariant or not. Time-invariant with respect to what?

The standard relational model and conventional normalization and
dependency theory cannot capture the connection between Emp tuples and
the real-world persons they represent. There is no real notion of
object identity (existence). When the key of a tuple changes its
value, there in no way of telling that the tuple still represent the
same real-world person. For example, if the tuple for Di, (Di, 30K),
is changed to (Jo, 30K) because Di changes name, we cannot capture
that both tuples belong to the same person and that Name thus is
time-varying.

One solution is to extend the relational model and use surrogates
(system-generated, unique identifiers with values that cannot be seen
but only compared for equality). The use of surrogates certainly works
in tuple-stamped models and should also work in attribute-value
stamped models.

Best regards,
Christian

\documentstyle[11pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This paper is intended to evolve into the first version of the TSQL
% benchmark.
% The purpose of this draft is to settle on a database instance for
% the already agreed-upon database schema.
% The purpose of the following draft is then to define a taxonomy to
% be used for categorizing the benchmark queries that will follow.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\addtolength{\textwidth}{1.485in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\addtolength{\topmargin}{-.85in}
\addtolength{\textheight}{1.8in}

\newenvironment{prog} { \begin{center} \begin{minipage}{3in}
\begin{tabbing} nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=\kill
}{\end{tabbing} \end{minipage} \end{center}}

\long\def\comment#1{}
\newcommand{\mvd}{\mbox{$\rightarrow \!\!\! \rightarrow \;$}}
\newcommand{\autsp}{$\;\;\;$}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PAPER START
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{\Large\bf The TSQL Benchmark \\ DRAFT}
\author{James Clifford \autsp Shashi K.~Gadia \autsp Fabio Grandi
  \autsp Christian S.~Jensen \\ Patrick Kalua \autsp Sunil Nair \autsp
  Edward Robertson \autsp John F.~Roddick \\ Maria Rita Scalas \autsp
  Richard T.~Snodgrass \autsp Abdullah Tansel \autsp Paolo Tiberio
  \autsp Gene Wuu}

%Note that the list of authors is preliminary and may not be accurate!

\date{April 8, 1993}
\maketitle

\section{Introduction}

\subsection{Goal}

The central goal of this document is to provide the temporal database
community with a {\em comprehensive consensus benchmark} for temporal
query languages that is {\em independent} of any existing language
proposal.

This is not a performance benchmark, but is rather a {\em semantic}
benchmark intended to be an aid in evaluating the user-friendliness of
proposals for temporal query languages. Thus, temporal query languages
should ideally be able to express the benchmark queries both
conveniently and naturally.

To obtain a consensus benchmark, researchers in temporal databases
have been invited to participate in this initiative, and each researcher
that has contributed significantly will be a coauthor. The electronic
mail distribution {\tt [e-mail]} is used as the medium for
discussing the benchmark and related issues.

As a consequence of the central goal above, no existing temporal data
models are used or mentioned. The relation schemas of the benchmark
are expressed as sets of attributes, including one attribute
illustrating user-defined time. However, the underlying temporal
aspects are implicit (of course, specific temporal data models might
add explicit temporal attributes). The contents of the relations are
described in natural language. The benchmark queries are also given
only in natural language.

The benchmark is {\em not} intended to constitute a metric for query
language completeness, and as such it is not a substitute for a
rigorous {\em theoretical} study of expressive powers of various
temporal query languages. Comprehensiveness of the benchmark is
desirable only to ensure that all aspects of query language design are
covered.

It it emphasized that using the benchmark as an advanced, quantitative
scoring system for comparing languages makes little sense. Thus, one
language is not necessarily superior to another just because one is
capable of expressing more benchmark queries than the other. Rather,
the focus is on user-friendliness.

\subsection{Scope}

Within certain boundaries, discussed next, the benchmark is intended
to contain all queries that appear reasonable and that are consistent
with the schema and data of the benchmark.

First, the benchmark is of a semantic nature---in its current form, it
is not aimed at performance comparisons. The intention is to provide a
foundation for comparing the descriptive and operational
characteristics and capabilities of temporal query languages, not
their performance characteristics. Properly extended with additional
relation schemas and a variety of large instances, the benchmark can
also be used for performance comparisons.

Second, a number of restrictions are imposed on which types of queries
are admissible in this version of the benchmark, including the
following.

\begin{itemize}
\item Queries are restricted to valid time only. Transaction-time
  related queries are not explored.

\item Schema evolution and versioning are not considered.

\item Incompleteness is not considered.

\item Recursive queries are not included.

\item General temporal reasoning is beyond the scope of this version
  of the benchmark.

\item Queries involving aggregation facilities are not considered.

\item Only queries are included---updates are not considered.

\comment{
\item Queries involving relations with multivalued dependencies (in
  the snapshot sense) are not explored.}

\comment{
\item User-defined time, including the interaction between
  user-defined time and valid time, is not considered.}

\comment{
\item Queries involving complex data retrieval are excluded.}

\comment{
\item Inheritance at both the schema and data levels is not
  considered.}

\comment{
\item Nested queries are not included.}

\comment{
\item For simplicity, each relation is used only once in each query.}

\end{itemize}

These advanced aspects are excluded solely for pragmatic reasons, and
the exclusion is not meant to imply in any way that the aspects are
not important. The restrictions simply represent an attempt to reduce
the size of the initial benchmark to manageable proportions.

It is emphasized that this benchmark is merely the first in a sequence
of ever-more comprehensive benchmarks. Later benchmarks will relax the
above restrictions on the scope of comprehensiveness imposed on this
benchmark. Specifically, the next version of the benchmark is intended
to include queries that involve aggregation.

\comment{
Specifically, the next version of the benchmark is intended to include
queries that use the same relation more than once, utilize
aggregation, and involve both valid time and user-defined time.}

\section{The Benchmark Database Schema}

\subsection{Criteria}

A suitable database schema for the benchmark should satisfy four
criteria.

\begin{itemize}
\item{} The schema should be natural. That is, it should correspond to
  a reasonable, though possibly greatly simplified, segment of the
  real world. This both reduces the need to explain the model and
  enhances the ability to recognize verball pitfalls in the path to
  the query instances.

\item{} The schema should be simple. This will aid in making the
  benchmark easy to understand. This criterion restricts the number of
  relation schemas and the number of attributes of the individual
  schemas. Additionally, the names of the relations and of the
  attributes should be short, as they will be referenced repeatedly.

  When an extension is proposed, the benefits should be carefully
  compared with the added complexity.

\item{} The schema should allow for comprehensiveness within the
  chosen scope. Using the schema, it should be possible formulate
  queries of all the types that appear reasonable.

  This indicates a need for at least two related relation schemas (for
  natural join queries).

\item{} A schema that has already been used frequently is preferred
  over a new schema. This guarantees that many existing queries can be
  adapted easily to the benchmark.

\item{} For clarity, schema and attribute names must start with
  capital letters.
\end{itemize}

\subsection{The Schema}

The database schema consists of three valid-time relation schemas,
{\tt Emp}, {\tt Skills}, and {\tt Dept}. They are defined as follows.

Relation {\tt Emp} uses the attributes {\tt Name}, {\tt Salary}, and
{\tt Dept} for recording the salaries of employees and the departments
where they work. In addition, it contains attributes {\tt Gender} and
{\tt D-birth} which indicate the gender and date of birth of an
employee. While the salary and department of an employee varies over
time, both {\tt Gender} and {\tt D-birth} are time-invariant.

Relation {\tt Skills} records the association of employees with skills
via the two attributes {\tt Name} and {\tt Skill}. The skills of an
employee may vary over time. For example, employees are considered to
have the skill ``driving'' only during those interval(s) when they
hold valid licenses.

Relation {\tt Dept} records the association of employees, as managers,
with departments, and it contains three attributes, {\tt Department},
recording a department name, {\tt Manager}, recording the manager of
the department, and {\tt Budget}, recording the budget of the
department.

Attributes {\tt Name}, {\tt Dept}, {\tt Department}, {\tt Skill}, and
{\tt Manager} are of type {\tt textString}; attribute {\tt Gender} is
one of {\tt F} (female) and {\tt M} (male); {\tt Salary} and {\tt
  Budget} are of type {\tt integer}; and {\tt D-birth} is a
user-defined time value which may be compared with valid times.

The relation schemas obey the following {\em snapshot} functional
and multivalued dependencies:

\begin{prog}
For {\tt Emp}: \\
\> {\tt Name} $\rightarrow$ {\tt Salary} \\
\> {\tt Name} $\rightarrow$ {\tt Dept} \\
\> {\tt Name} $\rightarrow$ {\tt Gender} \\
\> {\tt Name} $\rightarrow$ {\tt D-birth} \\
For {\tt Skills}: \\
\> {\tt Name} $\mvd$ {\tt Skill} (and {\tt Name} $\not\rightarrow$
{\tt Skills}) \\
For {\tt Dept}: \\
\> {\tt Department} $\rightarrow$ {\tt Manager} \\
\> {\tt Manager} $\rightarrow$ {\tt Department} \\
\> {\tt Department} $\rightarrow$ {\tt Budget}
\end{prog}

Note that {\tt Name} is the primary key of {\tt Emp} (it is the only
candidate key). For {\tt Skills}, there is no non-trivial key. For
{\tt Dept}, each of {\tt Department} and {\tt Manager} is a candidate
key, and {\tt Department} is selected as the primark key.

Each of the relation schemas are in snapshot Boyce-Codd normal form.

The attribute {\tt Manager} of {\tt Dept} is a foreign key for the
attribute {\tt Name} of {\tt Emp}. Thus, a tuple is allowed to exist
in the {\tt Dept} relation only if, for each non-empty snapshots of
this tuple, the {\tt Manager} attribute value exists as a {\tt Name}
value of some tuple in the simultaneous snapshot of the {\tt Emp}
relation.

\section{The Benchmark Data}

\subsection{Criteria}

\begin{itemize}
\item{} For simplicity and ease of typing, attribute values should be
  short and salary values should be multiples of \$10,000.

\item{} Transitions (i.e., timestamp values) occur only at the
  beginning of the month, and all dates should be in the time interval
  from 1/1/81 to 12/31/88 (because the digits 8 and 9 are relatively
  hard to distinguish). Time intervals are all specified by the
  inclusive starting and ending events. Also for clarity, relation
  instance names should start with lowercase letters.

\item{} The data should include a ``hole in the history'' of some
  entity. For example, the database may be designed to contain a whole
  in the employment of some employee.

\item{} The data should include asynchronous behavior of attributes.
  For example, the department and salary of employees may change
  independently.
\end{itemize}

\subsection{The Proposed Data}

Three instances, {\tt emp}, {\tt skills}, and {\tt dept}, are defined
over the {\tt Emp}, {\tt Skills}, and {\tt Dept} relation schemas,
respectively. The contents of these instances is described below.

There are two employees, Ed and Di.

Ed worked in the Toy department from 2/1/82 to 1/31/87, and in the
Book department from 4/1/87 to the present. His salary was \$20K from
2/1/82 to 5/31/82, then \$30K from 6/1/82 to 1/31/85, then \$40K from
2/1/85 to 1/31/87 and 4/1/87 to the present. Ed is male and was born
on 7/1/55. Several skills are recorded for Ed. He has been qualified
for typing since 4/1/82 and qualified for filing since 1/1/85. He was
qualified for driving from 1/1/82 to 5/1/82 and from 6/1/84 to
5/31/88.

Di worked in and managed the Toy department from 1/1/82 to the
present. The budget of the Toy department was \$150K from 1/1/82 to
7/31/84, \$200K from 8/1/84 to 12/31/86, and \$100K from 1/1/87 to the
present. Her salary was \$30K from 1/1/82 to 7/31/84, \$40K from
8/1/84 to 8/31/86, then \$50K from 9/1/86 to the present. Di is female
and was born on 10/1/60. Di has been qualified for directing from
1/1/82 to the present.

\end{document}